package offerbook;

import utils.ListNode;

/**
 * case1:链表1->2->3->3->4->4->5 处理后为 1->2->3->4->5
 * case2:链表1->2->3->3->4->4->5 处理后为 1->2->5
 * @date 2020/3/12 18:56
 */
public class Code57_DeleteRepeatNode {
    public static ListNode deleteDuplication1(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode pre = head;
        ListNode after = head.next;
        while (after != null){
            if(pre.val == after.val){
                pre.next = after.next;
                //let GC
                after.next = null;
                //pre不用变
                after = pre.next;
            }else {
                pre = after;
                after = after.next;
            }
        }
        return head;
    }
    public static ListNode deleteDuplication2(ListNode head) {
        if(head == null || head.next == null) return head;
        boolean repeat = false;
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        ListNode pre = head;//pre标识第一个重复节点
        while (pre != null){
            ListNode next = pre.next;
            //cur是重复的第一个节点，next是非重复节点
            while (next != null && pre.val == next.val){
                next = next.next;
                repeat = true;
            }
            if(repeat){//重复了，则不管pre到next前面那个
                pre = next;
                repeat = false;
            }else {
                //否则连接起来
                cur.next = pre;
                cur = cur.next;
                pre = next;
            }

        }
        //这里一定要有，cur是最后一个非重复的，如果后面都重复了，cur.next要断开
        cur.next = null;
        return newHead.next;
    }
    //递归
    public static ListNode deleteDuplication3(ListNode head) {
        if(head == null || head.next == null) return head;

        if(head.val == head.next.val){
            ListNode next = head.next;
            while (next != null && head.val == next.val)  next = next.next;
            //当前next和head不等了，head - next.pre都不要
            return deleteDuplication3(next);
        }else {
            head.next = deleteDuplication3(head.next);
            return head;
        }
    }
    public static void main(String[] args) {
        ListNode pHead = new ListNode(1);
        pHead.next = new ListNode(1);
        pHead.next.next = new ListNode(2);
        pHead.next.next.next = new ListNode(3);
        pHead.next.next.next.next = new ListNode(3);
        pHead.next.next.next.next.next = new ListNode(4);
        pHead.next.next.next.next.next.next = new ListNode(5);
        pHead.next.next.next.next.next.next.next = new ListNode(5);
//        deleteDuplication1(pHead);
        pHead = deleteDuplication2(pHead);
        while (pHead!=null){
            System.out.print(pHead.val + " ");
            pHead = pHead.next;
        }
    }

}
